#include <iostream>
#include <vector>

using namespace std;
/**
 * @brief
 * 2 <= letters.length <= 104
letters[i] 是一个小写字母
letters 按非递减顺序排序
letters 最少包含两个不同的字母
target 是一个小写字母
 *
 */
class Solution
{
public:
    char nextGreatestLetter(vector<char> &letters, char target)
    {
        for (char letter : letters)
        {
            if (letter > target)
            {
                return letter;
            }
        }
        return letters[0];
    }

    char nextGreatestLetter_3(vector<char> &letters, char target)
    {
        return target < letters.back() ? *upper_bound(letters.begin(), letters.end() - 1, target) : letters[0];
    }

    char nextGreatestLetter(vector<char> &letters, char target)
    {
        if (target < letters[0] || target >= letters.back())
           { return letters[0];}
      
        int left = 0, right = letters.size(), mid;
        while (right - left > 1)
        {
            mid = left + (right - left) / 2;
            if (letters[mid] <= target)
                left = mid;
            else
                right = mid;
        }
        return letters[right];
    }
};
int main()
{
    Solution s;
    vector<char> letters = {'c', 'f', 'j'};
    char target = 'a';
    cout << s.nextGreatestLetter(letters, target) << endl;
    system("pause");
    return 0;
}
